Class sjl.Deque
All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class sjl.Deque

java.lang.Object
   |
   +----sjl.Deque

public class Deque
extends Object
implements ReversibleContainer, QueueContainer
Deque is a kind of sequence that, like vector, supports random access iterators. In additition it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time. As with vectors, storage management is handled automatically.

insert and push invalidates all the iterators and references to the deque. In the worst case, inserting a single element into a deque takes time linear in the minimum of the distance from the insertion point to the beginning of the deque and the distance from the insertion point to the end of the deque. Inserting a single element either at the beginning or at the end of a deque always takes constant time. That is, a deque is especially optimized for pushing and popping elements at the beginning and end.

erase and pop invalidates all the iterators and references to deque.

Copyright © 1996 Finn Bock


Variable Index

 o buffer_size
Private.
 o BufferSize
The size of the second level buffer.
 o map
Private.
 o map_size
Private.
 o MapSize
The size of the first level array.

Constructor Index

 o Deque()
Construct a new empty Deque.
 o Deque(Deque)
Construct a new Deque with the size and contents of another deque.
 o Deque(ForwardIterator, ForwardIterator)
Construct a new Deque with the contents of the range [first,last).
 o Deque(int, Object)
Construct a new Deque with an initial size of size elements, each element initialized to with a reference to value.

Method Index

 o back()
Return the last element in the container.
 o begin()
Returns the iterator that represents the beginning of the deque.
 o beginGeneric()
Returns the iterator that represents the beginning of the deque as an untyped iterator.
 o beginRef()
Returns a reference to the iterator that represents the beginning of the deque.
 o empty()
Returns true if the deque does not contain any elements.
 o end()
Returns the iterator that represents the end of the deque.
 o endGeneric()
Returns the iterator that represents the end of the deque as an untyped iterator.
 o endRef()
Returns a reference to the iterator that represents the end of the deque.
 o equals(Object)
Compare the elements in this container with the elements in another container.
 o erase(Iterator)
Removes the element specified by position.
 o erase(Iterator, Iterator)
Removes the elements in the specified range.
 o flush()
Erase all the elements in the container.
 o front()
Return the first element in the container.
 o get(int)
Returns the nth element in the container.
 o insert(Iterator, InputIterator, InputIterator)
The elements in the range [first,last) are inserted into deque at the specified position.
 o insert(Iterator, int, Object)
Insert n references to element into the deque at the specified position.
 o insert(Iterator, Object)
Insert an element into the deque at the specified position.
 o max_size()
Returns the maximum number of elements that can be stored in a deque.
 o pop_back()
Removes the last element in deque.
 o pop_front()
Removes the first element in deque.
 o push_back(Object)
Add an element to the end of the deque.
 o push_front(Object)
Add an element to the front of the deque.
 o put(int, Object)
Set the nth element in the container to o.
 o rbegin()
Returns a copy of the reverse iterator that represents the beginning (end) of the list.
 o rbeginGeneric()
Returns a copy of the reverse iterator that represents the beginning (end) of the list as an untyped Iterator.
 o rend()
Returns a copy of the iterator that represents the end (beginning) of the list.
 o rendGeneric()
Returns a copy of the iterator that represents the end (beginning) of the list as an untyped Iterator.
 o size()
Returns the number of elements stored in the deque.
 o toString()
Returns the string representation of this deque.

Variables

 o MapSize
  public static int MapSize
The size of the first level array. All new Deque containers are created with an initial map with a size of MapSize. The default value is 256.
 o BufferSize
  public static int BufferSize
The size of the second level buffer. All new Deque containers are created with buffers with a size of BufferSize. The default value is 256.
 o map
  protected Object map[][]
Private. The actual data array.
 o map_size
  protected int map_size
Private. The actual map size.
 o buffer_size
  protected int buffer_size
Private. The actual buffer size.

Constructors

 o Deque
  public Deque()
Construct a new empty Deque.
 o Deque
  public Deque(int size,
               Object value)
Construct a new Deque with an initial size of size elements, each element initialized to with a reference to value.
Parameters:
size - The size of the new deque.
value - The initial value of each element in the deque.
 o Deque
  public Deque(Deque deque)
Construct a new Deque with the size and contents of another deque.
Parameters:
deque - The deque which is copied into the new deque.
 o Deque
  public Deque(ForwardIterator first,
               ForwardIterator last)
Construct a new Deque with the contents of the range [first,last).
Parameters:
first - The beginning of the range.
last - The end of the range.

Methods

 o flush
  public void flush()
Erase all the elements in the container.
 o equals
  public boolean equals(Object container)
Compare the elements in this container with the elements in another container.
Returns:
true is the elements match.
Overrides:
equals in class Object
 o begin
  public DequeIterator begin()
Returns the iterator that represents the beginning of the deque.
 o beginRef
  public DequeIterator beginRef()
Returns a reference to the iterator that represents the beginning of the deque.
 o end
  public DequeIterator end()
Returns the iterator that represents the end of the deque.
 o endRef
  public DequeIterator endRef()
Returns a reference to the iterator that represents the end of the deque.
 o beginGeneric
  public ForwardIterator beginGeneric()
Returns the iterator that represents the beginning of the deque as an untyped iterator.
 o endGeneric
  public ForwardIterator endGeneric()
Returns the iterator that represents the end of the deque as an untyped iterator.
 o rbegin
  public ReverseRandomIterator rbegin()
Returns a copy of the reverse iterator that represents the beginning (end) of the list.
 o rend
  public ReverseRandomIterator rend()
Returns a copy of the iterator that represents the end (beginning) of the list.
 o rbeginGeneric
  public Iterator rbeginGeneric()
Returns a copy of the reverse iterator that represents the beginning (end) of the list as an untyped Iterator.
 o rendGeneric
  public Iterator rendGeneric()
Returns a copy of the iterator that represents the end (beginning) of the list as an untyped Iterator.
 o size
  public int size()
Returns the number of elements stored in the deque.
 o max_size
  public int max_size()
Returns the maximum number of elements that can be stored in a deque.
 o empty
  public boolean empty()
Returns true if the deque does not contain any elements.
 o get
  public Object get(int n)
Returns the nth element in the container.
 o put
  public Object put(int n,
                    Object o)
Set the nth element in the container to o.
 o front
  public Object front()
Return the first element in the container.
 o back
  public Object back()
Return the last element in the container.
 o push_front
  public void push_front(Object o)
Add an element to the front of the deque.
 o push_back
  public void push_back(Object o)
Add an element to the end of the deque.
 o pop_front
  public void pop_front()
Removes the first element in deque.
 o pop_back
  public void pop_back()
Removes the last element in deque.
 o insert
  public Iterator insert(Iterator position,
                         Object o)
Insert an element into the deque at the specified position. Elements located after the position are moved.
Parameters:
position - insert the element at this position.
o - the element to insert.
Returns:
An iterator to the position where the element was inserted.
 o insert
  public void insert(Iterator position,
                     int n,
                     Object o)
Insert n references to element into the deque at the specified position. Elements located after the position are moved.
Parameters:
position - insert the element at this position.
n - the number of elements to insert.
o - the element to insert.
 o insert
  public void insert(Iterator position,
                     InputIterator first,
                     InputIterator last)
The elements in the range [first,last) are inserted into deque at the specified position. Elements located after the position are moved.
Parameters:
position - insert the element at this position.
first - the beginning of the range.
last - the end of the range.
 o erase
  public void erase(Iterator position)
Removes the element specified by position.
 o erase
  public void erase(Iterator first,
                    Iterator last)
Removes the elements in the specified range.
Parameters:
first - the beginning of the range.
last - the end of the range.
 o toString
  public String toString()
Returns the string representation of this deque.
Overrides:
toString in class Object

All Packages  Class Hierarchy  This Package  Previous  Next  Index